
//g++ linked_list.cpp -o linked_list -std=gnu++0x

/*
Next Todo:
1) Refactor code.
2) Check for possible naming discrepencies.
3) if .. else, while(){ ... } .. statements formation discrepencies.
4) Commenting in code need not be useless. Remove comments that are not necessary.
5) Check with standard linked list API so that any other missed functions can be implemented.
6) Implement some more functionalities:
	# Insert data in a sorted linked list 
	# Sort with whole node replacing. Not only the data (As implemented right now)
	# Sort with different sorting algorithms. !!(Selection sort, merge sort ? )
	# Perform various operations such as: 
		$ Checking whether the list is EMPTY
		$ Modify information of a node.
		$ Determine size of the list
		$ Create the list by reading input from a file
		$ Convert the implementation to OOP paradigm.
		$ Implement 'Stack' and 'Queue' with the current implementation of linked list.
*/


#include <iostream>
#include <cstdio>
#include <cctype>

using namespace std;

struct LinkedList{
	int data;
	LinkedList *next; 
};

LinkedList *g_p_head (nullptr);//points to the beginning of the list
LinkedList *pTrvrs (nullptr);//pointer to use while traversing the list. Every time before use 'pTrvrs = g_p_head' is done
LinkedList *pPrevElement (nullptr);//points to the last element of the list after traversing through the list is completed

//Adds element at the end of the list
bool push_back(int tempVariable);
//Traverses through the list and print data
void traverseListAndPrintData();
//Remove last item (at the far of the list) from list
bool removeFromBack();
//Adds element at the front of the list
bool push_front(int tempVariable);
//Remove records from front of the list 
bool removeFromFront();
//Remove list element from specified index (Considering the list is an array)
bool removeAt(int i);
//Print data at console given a specified index (Considering it an array)
bool dataAt(int i);
//Remove the specified data from list. Based on boolean 'removeAllOccurancesOfTheElement' all occurrences of the data
bool remove(int data, bool removeAllOccurancesOfTheElement);
//Remove list element from specified index (Considering the list is an array)
bool removeNthNode(int nNodeNumber);
//Remove Element
bool remove(bool removeFromFront);
//Find all occurrences of the data from the linked list
bool find(int dataToSearch);
//void sortLinkedList(bool ascendingOrder);
void sortLinkedList();

int main ()
{
	cout<<"HOW MANY INTEGERS DO YOU WISH TO ENTER TO THE BACK OF THE LIST"<<endl<<"-> ";
	
	int nNumberOfIntegers = 0;
	cin>>nNumberOfIntegers;
	cout<<endl<<endl<<"ENTER INTEGERS TO ENTER TO LIST"<<endl<<"-> ";
	
	//Read FROM FILE
	int tempVariable = 0;
	for(int i = 0; i <nNumberOfIntegers; i++)
	{
		cin>>tempVariable;
		if(!push_back(tempVariable))
			return 0;//Unsuccessful memory allocation; So quit program
		cout<<"-> ";
	}
	
	//Display list data by traversing through the list
	traverseListAndPrintData();
	
	cout<<"Do you want to remove list element from list ? (Y/N)"<<endl;
	
	char isRemove = 0;
	
	while((cin>>isRemove) && (toupper(isRemove) == 'Y'))
	{
		removeFromBack()?cout<<"ELEMENT FROM THE BACK OF THE LIST HAS BEEN REMOVED"<<endl:cout<<"ELEMENT DELETION PROCESS UNSUCCESSFUL"<<endl;
		cout<<"Do you want to remove list element from list ? (Y/N)"<<endl;
	}
	
	traverseListAndPrintData();
	
	cout<<"HOW MANY INTEGERS DO YOU WISH TO ENTER TO THE FRONT OF THE LIST"<<endl<<"-> ";
	
	nNumberOfIntegers = 0;
	cin>>nNumberOfIntegers;
	cout<<endl<<endl<<"ENTER INTEGERS TO ENTER TO LIST"<<endl<<"-> ";
	
	//Read FROM FILE
	tempVariable = 0;
	for(int i = 0; i <nNumberOfIntegers; i++)
	{
		cin>>tempVariable;
		if(!push_front(tempVariable))
			return 0;//Unsuccessful memory allocation; So quit program
		cout<<"-> ";
	}
	
	//Display list data by traversing through the list
	traverseListAndPrintData();
	
	cout<<"HOW MANY RECORDS YOU WANT TO REMOVE FROM FRONT"<<endl;
	
	tempVariable = 0;
	cin>>tempVariable;
	
	for(int i =0; i<tempVariable; i++){removeFromFront();}
	
	//Display list data by traversing through the list
	traverseListAndPrintData();
	
	cout<<"DO YOU WANT TO REMOVE LIST ELEMENT FROM LIST BY ELEMENT INDEX (Indexing 0 based)? (Y/N)"<<endl;
	
	isRemove = 0;
	while((cin>>isRemove) && (toupper(isRemove) == 'Y'))
	{
		cout<<"SPECIFY LIST INDEX TO REMOVE FROM LIST"<<endl<<"-> ";
		
		cin>>tempVariable;
		removeAt(tempVariable)?cout<<"ELEMENT FROM THE SPECIFIED INDEX OF THE LIST HAS BEEN REMOVED"<<endl:cout<<"ELEMENT DELETION PROCESS UNSUCCESSFUL"<<endl;
		
		traverseListAndPrintData();
		cout<<"Do you want to remove list element from list ? (Y/N)"<<endl;
	}
	
	traverseListAndPrintData();
	
	cout<<"WANT TO GET DATA AT A SPECIFIED INDEX ? (Y/N)"<<endl;
	isRemove = 0;
	while((cin>>isRemove) && (toupper(isRemove) == 'Y'))
	{
		cout<<"SPECIFY LIST INDEX"<<endl<<"-> ";
		
		cin>>tempVariable;
		dataAt(tempVariable)?cout<<"ELEMENT SEARCH SUCCESSFUL"<<endl:cout<<"ELEMENT SEARCH UNSUCCESSFUL"<<endl;
		
		cout<<"WANT TO GET DATA AT A SPECIFIED INDEX ? (Y/N)"<<endl;
	}
	
	traverseListAndPrintData();
	
	cout<<"WANT TO REMOVE DATA ? (Y/N)"<<endl;
	isRemove = 0;
	while((cin>>isRemove) && (toupper(isRemove) == 'Y'))
	{
		cout<<"ENTER DATA TO REMOVE"<<endl<<"-> ";
		
		cin>>tempVariable;
		remove(tempVariable, false)?cout<<"DATA REMOVAL SUCCESSFUL"<<endl:cout<<"DATA REMOVAL UNSUCCESSFUL"<<endl;
		
		traverseListAndPrintData();
		cout<<"WANT TO REMOVE DATA ? (Y/N)"<<endl;
	}
	
	traverseListAndPrintData();
	
	cout<<"WANT TO REMOVE ALL OCCURRENCES OF SPECIFIED DATA ? (Y/N)"<<endl;
	isRemove = 0;
	while((cin>>isRemove) && (toupper(isRemove) == 'Y'))
	{
		cout<<"ENTER DATA TO REMOVE"<<endl<<"-> ";
		
		cin>>tempVariable;
		remove(tempVariable, true)?cout<<"DATA REMOVAL SUCCESSFUL"<<endl:cout<<"DATA REMOVAL UNSUCCESSFUL"<<endl;
		
		traverseListAndPrintData();
		cout<<"WANT TO REMOVE ALL OCCURRENCES OF SPECIFIED DATA ? (Y/N)"<<endl;
	}
	
	traverseListAndPrintData();
	
	cout<<"WANT TO FIND ALL OCCURRENCES OF SPECIFIED DATA ? (Y/N)"<<endl;
	isRemove = 0;
	while((cin>>isRemove) && (toupper(isRemove) == 'Y'))
	{
		cout<<"ENTER DATA TO SEARCH"<<endl<<"-> ";
		
		cin>>tempVariable;
		find(tempVariable)?cout<<"DATA SEARCH SUCCESSFUL"<<endl:cout<<"DATA SEARCH UNSUCCESSFUL"<<endl;
		
		traverseListAndPrintData();
		cout<<"WANT TO FIND ALL OCCURRENCES OF SPECIFIED DATA ? (Y/N)"<<endl;
	}
	
	traverseListAndPrintData();
	
	sortLinkedList();
	
	traverseListAndPrintData();
	
	return 0;
}

bool push_back(int tempVariable)
{
	//List is empty. So first element is going to be added to the list
	if(g_p_head == nullptr)
	{
		//Allocate space for new item in the heap
		g_p_head = new LinkedList;
		
		//The following line of code can't find out whether memory allocation is successful or not !!
		//Use EXCEPTION instead
		//http://www.informit.com/articles/article.aspx?p=30642&seqNum=2
		
		//Memory allocation unsuccessful
		if(g_p_head == nullptr)
		{
			cout<<"Memory allocation unsuccessful"<<endl;
			return false;
		}
		
		g_p_head->data = tempVariable;
		g_p_head->next = nullptr;
	}
	else
	{
		pTrvrs = pPrevElement = nullptr;//Reset for readability 
		pTrvrs = g_p_head;//Start traversing from the first element
		while(pTrvrs != nullptr)
		{
			pPrevElement = pTrvrs;
			pTrvrs = pTrvrs->next;
		}
		
		//Allocate space for new item in the heap
		pPrevElement->next = new LinkedList;
		
		//The following line of code can't find out whether memory allocation is successful or not !!
		//Use EXCEPTION instead
		//http://www.informit.com/articles/article.aspx?p=30642&seqNum=2
		
		//Memory allocation unsuccessful
		if(pPrevElement->next == nullptr)
		{
			cout<<"Memory allocation unsuccessful"<<endl;
			return false;
		}
		
		//Store record
		pPrevElement->next->data = tempVariable;
		pPrevElement = pTrvrs = nullptr;//Reset pointers for further use
	}
	return true;
}

void traverseListAndPrintData()
{
	if(g_p_head == nullptr)
		cout<<"LINKED LIST IS EMPTY"<<endl;
	else
	{
		cout<<"OUTPUT DISPLAY:"<<endl;
		
		pTrvrs = nullptr;//Reset for readability
		pTrvrs = g_p_head;//Start traversing from first element 
		
		int i = 1;
		//Traverse until nullptr is found
		while(pTrvrs != nullptr)
		{
			cout<<"Data at Index #"<<(i++)<<" : "<<pTrvrs->data<<endl;
			pTrvrs = pTrvrs->next;
		}
		//pTrvrs = nullptr because of previous condition
	}
}

bool removeFromBack()
{
	//List is EMPTY
	if(g_p_head == nullptr)
	{
		cout<<"LIST IS EMPTY"<<endl<<"NO ITEM TO DELETE"<<endl;
		return false;
	}
	
	//List Has only 1 item
	if(g_p_head->next == nullptr)
	{
		//Hold list item memory to delete later
		LinkedList *pMemoryToDelete = g_p_head;
		
		//Reset header pointer as no item exists in the list now
		g_p_head = nullptr;
		
		//Release memory
		delete pMemoryToDelete;
		return true;
	}
	
	//Traverse through list to reach the last element of the list
	pTrvrs = g_p_head;
	pPrevElement = nullptr;
	
	while(pTrvrs->next != nullptr)
	{
		pPrevElement = pTrvrs;
		pTrvrs = pTrvrs->next;
	}
	
	//Point to the memory that is to be released later
	LinkedList *pMemoryToDelete = pTrvrs;
	
	//Make 2nd last element of the list to be NEW LAST element of the list
	pPrevElement->next = nullptr;
	
	//Release allocated memory of the last element
	delete pMemoryToDelete;
	return true;
}

bool push_front(int tempVariable)
{
	//List is empty. First element to insert
	if(g_p_head == nullptr)
	{
		g_p_head = new LinkedList;
		
		if(g_p_head == nullptr)
		{
			cout<<"Memory allocation unsuccessful"<<endl;
			return false;
		}
		
		g_p_head->data = tempVariable;
		g_p_head->next = nullptr;
		
		return true;
	}
	
	LinkedList *newlistItem = new LinkedList;
	
	if(newlistItem == nullptr)
	{
		cout<<"Memory allocation unsuccessful"<<endl;
		return false;
	}
		
	newlistItem->data = tempVariable;
	newlistItem->next = g_p_head;
	
	g_p_head = newlistItem;
	return true;
}

bool removeFromFront()
{
	if(g_p_head == nullptr){
		cout<<"LIST IS EMPTY. NO ITEM TO REMOVE"<<endl;
		return false;
	}
	
	LinkedList *pMemoryToDelete = g_p_head;
	g_p_head = g_p_head->next;
	delete pMemoryToDelete;
	return true;
}

bool removeAt(int i)
{
	if(g_p_head == nullptr){
		cout<<"LIST IS EMPTY. NO ITEM TO REMOVE"<<endl;
		return false;
	}
	
	int j = 0;
	pTrvrs = g_p_head;
	pPrevElement = nullptr;
	while(pTrvrs != nullptr){
		if(i == j){
			LinkedList *pMemoryToDelete = pTrvrs;
			if(pPrevElement == nullptr) //List contains only 1 element
				g_p_head = pTrvrs->next;
			else
				pPrevElement->next = pTrvrs->next;
			delete pMemoryToDelete;
			return true;
		}
		j++;
		pPrevElement = pTrvrs;
		pTrvrs = pTrvrs->next;
	}
	cout<<"PROVIDED INDEX IS GREATER THAN LIST LENGTH"<<endl;
	return false;
}

bool dataAt(int i)
{
	if(g_p_head == nullptr){
		cout<<"LIST IS EMPTY. NO ITEM TO SEARCH FOR"<<endl;
		return false;
	}
	int j =0;
	pTrvrs = g_p_head;
	while(pTrvrs != nullptr){
		if(i == j){
			cout<<"Data ["<<i<<"] :"<<pTrvrs->data<<endl;
			return true;
		}
		j++;
		pTrvrs = pTrvrs->next;
	}
	cout<<"PROVIDED INDEX IS GREATER THAN LIST LENGTH"<<endl;
	return false;
}

bool remove(int data, bool removeAllOccurancesOfTheElement)
{
	if(g_p_head == nullptr){
		cout<<"LIST IS EMPTY. NO ITEM TO REMOVE"<<endl;
		return false;
	}
	bool dataFound = false;
	pTrvrs = g_p_head;
	pPrevElement = nullptr;
	while(pTrvrs != nullptr){
		if(pTrvrs->data == data){
			if(!dataFound) dataFound = true;
			LinkedList *pMemoryToDelete = pTrvrs;
			//DATA HAS BEEN FOUND AT FIRST INDEX
			if(pPrevElement == nullptr)
				g_p_head = pTrvrs->next;
			else
				pPrevElement->next = pTrvrs->next;
			delete pMemoryToDelete;
			pTrvrs = nullptr;
			if(!removeAllOccurancesOfTheElement)
				return true;
		}
		//pTrvrs HAS BEEN DELETED FROM LIST
		if(pTrvrs == nullptr)
			if(pPrevElement == nullptr)//DATA HAS BEEN FOUND AT FIRST INDEX
				pTrvrs = g_p_head;
			else
				pTrvrs = pPrevElement->next;
		else{
			pPrevElement = pTrvrs;
			pTrvrs = pTrvrs->next;
		}
	}
	if(!removeAllOccurancesOfTheElement){
		cout<<"DATA NOT FOUND IN THE LIST"<<endl;
		return false;
	}
	else
		if(dataFound) return true;
		else{
			cout<<"DATA NOT FOUND IN THE LIST"<<endl;
			return false;
		}
}

bool removeNthNode(int nNodeNumber)
{
	return removeAt(nNodeNumber);
}

bool remove(bool removeFromFrontOfTheList)
{
	if(removeFromFrontOfTheList)
		return removeFromFront();
	else
		return removeFromBack();
}

bool find(int dataToSearch)
{
	if(g_p_head == nullptr){
		cout<<"LIST IS EMPTY. NO ITEM TO SEARCH FOR"<<endl;
		return false;
	}
	
	bool foundFirst = false;
	int i = 0;
	pTrvrs = g_p_head;
	while(pTrvrs != nullptr){
		if(pTrvrs->data == dataToSearch){
			if(!foundFirst){
					cout<<"FOUND DATA ACCORDING TO THEIR INDEX IS GIVEN BELOW"<<endl;
					foundFirst = true;
				}
				cout<<"Data ["<<(i+1)<<"] : "<<pTrvrs->data<<endl;
			}
		i++;
		pTrvrs = pTrvrs->next;
	}
	
	if(foundFirst)
		return true;
	else{
		cout<<"DATA DOESN'T EXIST IN THE LIST"<<endl;
		return false;
	}
}

void sortLinkedList()
{
	if((g_p_head == nullptr) || 
		(g_p_head->next == nullptr)) return;
	
	pTrvrs = g_p_head;
	int listElementCount= 0;
	while(pTrvrs != nullptr){
		listElementCount++;
		pTrvrs = pTrvrs->next;
	}
	
	for(int i =0; i<listElementCount; i++){
		pTrvrs = g_p_head;
		while(pTrvrs != nullptr){
			if((pTrvrs->next != nullptr) && (pTrvrs->data > pTrvrs->next->data)){//Extra != nullptr checking is needed as for the last element pTrvrs->next == nullptr
				int tmp = pTrvrs->data;
				pTrvrs->data = pTrvrs->next->data;
				pTrvrs->next->data = tmp;
			}
			pTrvrs = pTrvrs->next;
		}
	}
}
